package com.tju.eduservice.LeetCode;

import java.util.PriorityQueue;

public class MedianFinder {

    public static void main(String[] args) {
        MedianFinder queue = new MedianFinder();
        queue.addNum(23);
        queue.addNum(34);
        System.out.println(queue.findMedian());
    }







    PriorityQueue<Integer> queueMax ;
    PriorityQueue<Integer> queueMin ;
    int maxSize = 0;
    int minSize = 0;
    public MedianFinder() {
        queueMax = new PriorityQueue<>((o1,o2) -> o2 - o1);
        queueMin =  new PriorityQueue<>();
    }

    public void addNum(int num) {
        if(maxSize == 0){
            queueMax.offer(num);
            maxSize++;
            return;
        }
        if(maxSize >= minSize){
            if(queueMax.peek() <= num){
                queueMin.offer(num);
                minSize++;
            }else{
                queueMin.offer(queueMax.poll());
                queueMax.offer(num);
                minSize++;
            }
        }else{
            if(queueMin.peek() >= num){
                queueMax.offer(num);
                maxSize++;
            }else{
                queueMax.offer(queueMin.poll());
                queueMin.offer(num);
                maxSize++;
            }
        }

    }

    public double findMedian() {
        if(maxSize > minSize){
            return queueMax.peek() / 1.0;
        }else if(maxSize < minSize){
            return queueMin.peek() / 1.0;
        }else{
            return (queueMin.peek() + queueMax.peek()) / 2.0;
        }
    }
}
